package com.example.ac36;

/**
 * @description Sunday 算法
 * @auther lijiewei
 * @date 2022/1/20 11:58
 */
public class Sunday {

    private int ASCII_SIZE = 126;

    /**
     * 主串中查找模式串出现的位置
     * @param total 主串
     * @param part 模式串
     * @return
     * @author lijiewei
     * @date   2022/1/20 13:41
     */
    public int sunday(char[] total, char[] part) {
        int tSize = total.length;
        int pSize = part.length;
        //126位 ASCII 码，用于对应主串参与匹配最末位字符移动到该位需要移动的位数
        int[] move = new int[ASCII_SIZE];
        for (int i = 0; i < ASCII_SIZE; i++) {
            //如果该字符没有在模式串中出现则直接跳过，即 移动位数=模式串长度+1；
            move[i] = pSize+1;
        }

        for (int i = 0; i < pSize; i++) {
            //移动位数 = 模式串长度 - 该字符最右出现的位置（以0开始）
            //= 模式串中该字符最右出现的位置到尾部的距离 + 1
            move[part[i]] = pSize-i;
        }

        //模式串头部在字符串位置
        int s = 0;
        //模式串已经匹配了的长度
        int j = 0;

        //到达末尾之前
        while (s <= tSize-pSize) {
            //每次重新匹配都要重置已经匹配的长度
            j = 0;
            while (total[s+j] == part[j]) {
                j++;
                //完全匹配
                if (j >= pSize) {
                    return s;
                }
            }
            //存在字符不匹配,移动模式串开始匹配的位置 s
            s += move[total[s+pSize]];
        }
        return -1;
    }

}
